/**
*      author: Y_Yao
*      created: 2025-04-21 17:49:04
**/

#include<bits/stdc++.h>

#define int LL
using namespace std;
using LL = long long;
const LL LLINF = 9e18;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;

set<int> pri;
bool not_prime[N];

void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      pri.insert(i);
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        break;
      }
    }
  }
}
int n;
 
void solve()
{
    cin >> n;
    pre(N);
    for(int i = 1;i <= n;i++)
    {
        int x;
        cin >> x;

    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}